package org.example.优先级队列合并多个有序链表;

import org.example.ListNode;

/**
 * 使用小顶堆合并多个有序链表
 */
public class E01Leetcode23 {

    public static void main(String[] args) {
        ListNode[] list = {ListNode.of(1,2,3),ListNode.of(2,4,6),ListNode.of(3,7,8,9), null, null};
        ListNode node = new E01Leetcode23().mergeKLists(list);
        System.out.println(node.toString());
    }

    private ListNode mergeKLists(ListNode[] list) {
        MinHead minHead = new MinHead(list.length);
        // 1. 把链表的头节点加入到小顶堆中
        for (ListNode listNode : list) {
            if (listNode != null) {
                minHead.offer(listNode);
            }
        }

        // 2. 取出小顶堆的头节点放入新链表中，并把next个节点加入到小顶堆中
        ListNode s = new ListNode(-1, null);
        ListNode t = s;
        while (!minHead.isEmpty()) {
            ListNode min = minHead.poll();
            t.next = min;
            t = min;
            if (min.next != null) {
                minHead.offer(min.next);
            }
        }
        return s.next;
    }


}
